/**
 * 给定一个二叉树，找出其最大深度。
   二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 */


// 回溯法
// 遍历二叉树的所有路径，返回最长的路径值
let maxDepth = function(root) {
    if (!root) return 0;
    let res = [];
    let path = [];

    function recur(root) {
        if (!root) return;
        path.push(root.val);
        if (!root.left && !root.right) {
            res.push(path.concat());
        }
        recur(root.left);
        recur(root.right);
        path.pop();
    }
    recur(root);
    res = res.map(item => item.length);
    return Math.max(...res);

};

/** 深度优先DFS
 * 如果我们知道了左子树和右子树的最大深度 ll 和 rr，那么该二叉树的最大深度即为 max(l, r) + 1;
 * 而左子树和右子树的最大深度又可以以同样的方式进行计算。
 */
let maxDepth = function(root) {
    if (!root) return 0;
    let left = maxDepth(root.left);
    let right = maxDepth(root.right);
    return Math.max(left, right) + 1;
};